// #include<bits/stdc++.h>
// #define ll long long
// using namespace std;
// const int maxn=2e5+5;
// struct node
// {
//     ll mx,sum,t,sv,add,tag,len;
// };
// node tr[maxn<<2];
// int n,q;
// ll d[maxn<<2];
// inline void mdf(int id,int k,ll w)
// {
//     if(k==0)
//     {
//         tr[id].mx+=w;
//         tr[id].t+=w*w*tr[id].len+tr[id].sv*w+tr[id].sum*w;
//         tr[id].sum+=w*tr[id].len;
//         tr[id].sv+=w*tr[id].len;
//         tr[id].add+=w;
//     }
//     if(k==1)
//     {
//         tr[id].mx=w,tr[id].t=w*w*tr[id].len,tr[id].sum=w*tr[id].len,tr[id].sv=w*tr[id].len;
//         tr[id].add=0,tr[id].tag=w;
//     }
// }
// inline void pushdown(int id)
// {
//     if(tr[id].tag)
//     {
//         mdf(id<<1,1,tr[id].tag);
//         mdf(id<<1|1,1,tr[id].tag);
//     }
//     if(tr[id].add)
//     {
//         mdf(id<<1,0,tr[id].add);
//         mdf(id<<1|1,0,tr[id].add);
//     }
//     tr[id].tag=tr[id].add=0;
// }
// node calc(node nd,int id)
// {
//     node ret=nd;
//     if(tr[id].len==1)
//     {
//         ret.mx=max(ret.mx,tr[id].mx);
//         ret.sum+=tr[id].sum;
//         ret.t+=tr[id].sum*ret.mx;
//         ret.sv+=ret.mx;
//         ret.len+=tr[id].len;
//     }
//     else
//     {
//         pushdown(id);
//         if(tr[id<<1].mx>=nd.mx)
//         {
//             ret=calc(nd,id<<1);
//             ret.mx=max(ret.mx,tr[id<<1|1].mx);
//             ret.sum+=tr[id<<1|1].sum;
//             ret.t+=tr[id].t-tr[id<<1].t;
//             ret.sv+=tr[id].sv-tr[id<<1].sv;
//             ret.len+=tr[id<<1|1].len;
//         }
//         else
//         {
//             nd.sum+=tr[id<<1].sum;
//             nd.t+=tr[id<<1].sum*nd.mx;
//             nd.sv+=tr[id<<1].len*nd.mx;
//             nd.len+=tr[id<<1].len;
//             ret=calc(nd,id<<1|1);
//         }
//     }
//     return ret;
// }
// inline void pushup(int id)
// {
//     tr[id]=calc(tr[id<<1],id<<1|1);
//     tr[id].tag=tr[id].add=0;
// }
// void build(int id,int l,int r)
// {
//     if(l==r)
//     {
//         tr[id]=(node){d[l],d[l],d[l]*d[l],d[l],0,0,1};
//         return;
//     }
//     int mid=(l+r)>>1;
//     build(id<<1,l,mid);
//     build(id<<1|1,mid+1,r);
//     pushup(id);
// }
// void update(int id,int l,int r,int x,int y,int k,ll w)
// {
//     if(l>=x && r<=y)
//     {
//         mdf(id,k,w);
//         return;
//     }
//     int mid=(l+r)>>1;
//     pushdown(id);
//     if(x<=mid) update(id<<1,l,mid,x,y,k,w);
//     if(y>mid) update(id<<1|1,mid+1,r,x,y,k,w);
//     pushup(id);
// }
// int num[maxn],cnt,L[maxn],R[maxn];
// void get_num(int id,int l,int r,int x,int y)
// {
//     if(l>=x && r<=y)
//     {
//         cnt++;
//         num[cnt]=id,L[cnt]=l,R[cnt]=r;
//         return;
//     }
//     int mid=(l+r)>>1;
//     pushdown(id);
//     if(x<=mid) get_num(id<<1,l,mid,x,y);
//     if(y>mid) get_num(id<<1|1,mid+1,r,x,y);
// }
// int get_pos(int id,int l,int r,node nd,ll t)
// {
//     if(l==r) return l;
//     int mid=(l+r)>>1;
//     pushdown(id);
//     node dt=calc(nd,id<<1);
//     if(dt.t<=t) return get_pos(id<<1|1,mid+1,r,dt,t);
//     else return get_pos(id<<1,l,mid,nd,t);
// }
// int main()
// {
//     //system("fc training.out training6.ans /W");
//     //return 0;
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     //freopen("training6.in","r",stdin);
//     //freopen("training.out","w",stdout);
//     int fl;
//     node nd,dt;
//     char opt;
//     ll s,t,w;
//     cin>>n>>q;
//     for(int i=0;i<n;i++) cin>>d[i];
//     build(1,0,n-1);
//     while(q--)
//     {
//         cin>>opt>>s>>t;
//         if(opt=='P')
//         {
//             cin>>w;
//             if(s<=t) update(1,0,n-1,s,t,0,w);
//             else update(1,0,n-1,0,t,0,w),update(1,0,n-1,s,n-1,0,w);
//         }
//         if(opt=='R')
//         {
//             cin>>w;
//             if(s<=t) update(1,0,n-1,s,t,1,w);
//             else update(1,0,n-1,0,t,1,w),update(1,0,n-1,s,n-1,1,w);
//         }
//         if(opt=='Q')
//         {
//             fl=0,cnt=0,nd=(node){0,0,0,0,0,0,0};
//             get_num(1,0,n-1,s,n-1);
//             get_num(1,0,n-1,0,n-1);
//             for(int i=1;i<=cnt;i++)
//             {
//                 dt=calc(nd,num[i]);
//                 if(dt.t>t)
//                 {
//                     fl=1;
//                     cout<<get_pos(num[i],L[i],R[i],nd,t)<<'\n';
//                     break;
//                 }
//                 nd=dt;
//             }
//             if(fl==0) cout<<get_pos(1,0,n-1,nd,(t-nd.t)%(tr[1].sum*tr[1].mx)+nd.t)<<'\n';
//         }
//     }
//     return 0;
// }
int main(){
    
}